package Sort;

public class MergeSort {

    public static void sort(int[] arr){
        int[] merged = new int[arr.length];
        split(arr,0,arr.length-1,merged);
    }

    public static void split(int[] arr,int left,int right ,int[] merged){
        if(right==left) return ;

        int mid=(right+left) >>>1;
        split(arr,left,mid,merged);
        split(arr,mid+1,right,merged);
        merge(arr,left,mid,right,merged);

    }
    // 简化merge方法，只接收左右边界
    public static void merge(int[] nums, int left, int mid, int right, int[] merged) {
        int i = left;      // 左半部分起始
        int j = mid + 1;   // 右半部分起始
        int k = left;      // merged数组索引

        // 合并两个有序部分
        while(i <= mid && j <= right){
            if(nums[i] < nums[j]){
                merged[k++] = nums[i++];
            } else {
                merged[k++] = nums[j++];
            }
        }

        // 处理左半部分剩余元素
        while(i <= mid) {
            merged[k++] = nums[i++];
        }

        // 处理右半部分剩余元素
        while(j <= right) {
            merged[k++] = nums[j++];
        }

        // 将合并结果拷贝回原数组
        for(int index = left; index <= right; index++){
            nums[index] = merged[index];
        }
    }

}
